/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
private:
    ListNode *reverseList(ListNode* head){
        ListNode *prev = nullptr;
        ListNode *cur = head;
        while(cur != nullptr){
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(!head1) return head2;
        if(!head2) return head1;

        head1 = reverseList(head1);
        head2 = reverseList(head2);

        int carry = 0;
        ListNode *pos1 = head1;
        ListNode *pos2 = head2;
        ListNode *ret = nullptr;
        while(pos1 != nullptr || pos2 != nullptr || carry){
            int sum = carry;
            if(pos1){
                sum += pos1->val;
                pos1 = pos1->next;
            }
            if(pos2){
                sum += pos2->val;
                pos2 = pos2->next;
            }

            carry = sum / 10;
            int digit = sum % 10;
            
            ListNode *node = new ListNode(digit);
            node->next = ret;
            ret = node;
        }
        return ret;
    }
};